'''
https://leetcode.cn/problems/find-eventual-safe-states/description/?envType=study-plan-v2&envId=graph-theory
'''
from collections import deque
from typing import List


class Solution:
    # 节点只能到安全节点
    #   到不了或者有循环路就不算是安全节点
    # dfs+三色标记
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        state = [0] * n    # 0未访问，1访问中，2访问完(也表示了安全节点)
        def dfs(u):
            if state[u] != 0:
                return state[u] == 2
            state[u] = 1
            for v in graph[u]:
                if not dfs(v):
                    return False
            state[u] = 2
            return True
        return [u for u in range(n) if dfs(u)]

    # 反向建图 + 拓扑排序
    def eventualSafeNodes2(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        indegree = [0] * n
        for u in range(n):
            indegree[u] = len(graph[u])     # 原图的出度，反向图的入度
        reversed_graph = [[] for _ in range(n)]
        for u in range(n):
            for v in graph[u]:
                reversed_graph[v].append(u)
        q = []
        for u in range(n):
            if indegree[u] == 0:
                q.append(u)
        while q:
            u = q.pop()
            for v in reversed_graph[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)
        return [i for i in range(n) if indegree[i] == 0]








